package william.hash;

import java.util.HashMap;
import java.util.Map;

/**
 * @author ZhangShenao
 * @date 2024/3/6
 * @description <a href="https://leetcode.cn/problems/two-sum/description/">...</a>
 */
public class Leetcode1_两数之和 {
    /**
     * 使用Map实现
     * 使用一个Map,保存数组中的元素及其索引 key=元素值 value=元素的索引
     * 遍历数组,判断target-当前元素的值在Map中是否存在。
     * -如果存在,则将其索引与当前元素索引返回
     * -否则将当前元素及其索引保存在Map中,继续遍历数组
     * <p>
     * 时间复杂度O(N) 需要遍历一次数组
     * 空间复杂度O(N) 需要额外申请一个长度为N的Map
     */
    public int[] twoSum(int[] nums, int target) {
        //边界条件校验
        if (nums == null || nums.length < 2) {
            throw new IllegalArgumentException("invalid input!");
        }

        //使用一个Map,保存数组中的元素及其索引
        //key=元素值 value=元素的索引
        int N = nums.length;
        Map<Integer, Integer> cache = new HashMap<>(N);

        //遍历数组,判断target-当前元素的值在Map中是否存在。
        for (int i = 0; i < N; i++) {
            int minus = target - nums[i];
            if (cache.containsKey(minus)) { //如果存在,则将其索引与当前元素索引返回
                return new int[]{cache.get(minus), i};
            }

            //否则将当前元素及其索引保存在Map中,继续遍历数组
            cache.put(nums[i], i);
        }

        //未找到有效结果,直接抛异常
        throw new IllegalArgumentException("invalid input!");
    }
}
